﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Xml;

namespace Workflows.Components.TextMining.Clustering
{
    /// <summary>
    /// 
    /// </summary>
    public class ClusterResultReader
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,double> ReadClusterDistances(string xmlFilePath)
        {
            Dictionary<int,double> clusterDistances=new Dictionary<int, double>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList clusterNodes = xDoc.SelectNodes("Clusters/Cluster");
            foreach (XmlNode clusterNode in clusterNodes)
            {
                int clusterID = int.Parse(clusterNode.Attributes.GetNamedItem("ClusterID").Value);
                double distance = double.Parse(clusterNode.Attributes.GetNamedItem("Distance").Value);
                clusterDistances.Add(clusterID, distance);
            }
            return clusterDistances;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,List<int>> ReadClusterDocs(string xmlFilePath)
        {
            Dictionary<int,List<int>> clusterDocs=new Dictionary<int, List<int>>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList clusterNodes = xDoc.SelectNodes("Clusters/Cluster");
            foreach (XmlNode clusterNode in clusterNodes)
            {
                int clusterID = int.Parse(clusterNode.Attributes.GetNamedItem("ClusterID").Value);
                
                XmlNodeList docNodes = clusterNode.SelectNodes("Docs/Doc");
                if (docNodes != null && docNodes.Count > 0)
                {
                    foreach (XmlNode docNode in docNodes)
                    {
                        int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                        if (!clusterDocs.ContainsKey(clusterID))
                        {
                            List<int> docIDs=new List<int>();
                            docIDs.Add(docID);
                            clusterDocs.Add(clusterID,docIDs);
                        }
                        else
                        {
                            List<int> docIDs = clusterDocs[clusterID];
                            if(!docIDs.Contains(docID))
                                docIDs.Add(docID);
                            clusterDocs[clusterID] = docIDs;
                        }
                    }
                }
            }
            return clusterDocs;
        }

        /// <summary>
        /// docid -> clusterid
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,int> ReadDocClusters(string xmlFilePath)
        {
            Dictionary<int, int> docClusters=new Dictionary<int, int>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList clusterNodes = xDoc.SelectNodes("Clusters/Cluster");
            foreach (XmlNode clusterNode in clusterNodes)
            {
                int clusterID = int.Parse(clusterNode.Attributes.GetNamedItem("ClusterID").Value);

                XmlNodeList docNodes = clusterNode.SelectNodes("Docs/Doc");
                if (docNodes != null && docNodes.Count > 0)
                {
                    foreach (XmlNode docNode in docNodes)
                    {
                        int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                        docClusters.Add(docID,clusterID);
                    }
                }
            }
            return docClusters;
        }
        
        /// <summary>
        /// termid -> (docID -> tfidf weight)
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int, Dictionary<int, double>> ReadTermTfidfForDocuments(string xmlFilePath)
        {
            Dictionary<int, Dictionary<int, double>> tfidfWeights = new Dictionary<int, Dictionary<int, double>>();
            // termid -> (docid -> freq)
            Dictionary<int, Dictionary<int, int>> termDocFreqs = new Dictionary<int, Dictionary<int, int>>();
            Dictionary<int, List<int>> docTerms = new Dictionary<int, List<int>>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList docNodes = xDoc.SelectNodes("//Doc");
            List<int> allDocIDs = new List<int>();
            foreach (XmlNode docNode in docNodes)
            {
                int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                List<int> docTermIDs = new List<int>();
                if (docTerms.ContainsKey(docID))
                    docTermIDs = docTerms[docID];
                if (!allDocIDs.Contains(docID))
                    allDocIDs.Add(docID);
                XmlNodeList termNodes = docNode.SelectNodes("Term");
                foreach (XmlNode termNode in termNodes)
                {
                    int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                    int count = int.Parse(termNode.Attributes.GetNamedItem("Count").Value);
                    if (termDocFreqs.ContainsKey(termID))
                    {
                        Dictionary<int, int> termCountForDocs = termDocFreqs[termID];
                        if (!termCountForDocs.ContainsKey(docID))
                            termCountForDocs.Add(docID, count);
                        termDocFreqs[termID] = termCountForDocs;
                    }
                    else
                    {
                        Dictionary<int, int> termCountForDocs = new Dictionary<int, int>();
                        termCountForDocs.Add(docID, count);
                        termDocFreqs.Add(termID, termCountForDocs);
                    }
                    if (!docTermIDs.Contains(termID))
                        docTermIDs.Add(termID);
                }
                if (docTerms.ContainsKey(docID))
                    docTerms[docID] = docTermIDs;
                else
                    docTerms.Add(docID, docTermIDs);
            }

            foreach (int termID in termDocFreqs.Keys)
            {
                Dictionary<int, double> docTfidfWeights = new Dictionary<int, double>();

                Dictionary<int, int> docTermFreq = termDocFreqs[termID];
                double idf = Math.Log(((double)allDocIDs.Count / docTermFreq.Count), 2);
                foreach (int docID in docTermFreq.Keys)
                {
                    double tf = (double)docTermFreq[docID] / docTerms[docID].Count;
                    double tfidf = tf * idf;
                    docTfidfWeights.Add(docID, tfidf);
                }

                tfidfWeights.Add(termID, docTfidfWeights);
            }
            return tfidfWeights;
        }

        /// <summary>
        /// termid --> (docid --> freq)
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int, Dictionary<int, int>> ReadTermDocFrequencies(string xmlFilePath)
        {
            Dictionary<int, Dictionary<int, int>> termDocFreqs = new Dictionary<int, Dictionary<int, int>>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList docNodes = xDoc.SelectNodes("//Doc");
            foreach (XmlNode docNode in docNodes)
            {
                int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                XmlNodeList termNodes = docNode.SelectNodes("Term");
                foreach (XmlNode termNode in termNodes)
                {
                    int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                    int count = int.Parse(termNode.Attributes.GetNamedItem("Count").Value);
                    if (termDocFreqs.ContainsKey(termID))
                    {
                        Dictionary<int, int> termCountForDocs = termDocFreqs[termID];
                        if (!termCountForDocs.ContainsKey(docID))
                            termCountForDocs.Add(docID, count);
                        termDocFreqs[termID] = termCountForDocs;
                    }
                    else
                    {
                        Dictionary<int, int> termCountForDocs = new Dictionary<int, int>();
                        termCountForDocs.Add(docID, count);
                        termDocFreqs.Add(termID, termCountForDocs);
                    }

                }
            }
            return termDocFreqs;
        }

        /// <summary>
        /// docid -> (termid -> freq)
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,Dictionary<int,int>> ReadDocTermFrequencies(string xmlFilePath)
        {
            Dictionary<int, Dictionary<int, int>> docTermFreqs = new Dictionary<int, Dictionary<int, int>>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList docNodes = xDoc.SelectNodes("//Doc");
            foreach (XmlNode docNode in docNodes)
            {
                int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                XmlNodeList termNodes = docNode.SelectNodes("Term");
                foreach (XmlNode termNode in termNodes)
                {
                    int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                    int count = int.Parse(termNode.Attributes.GetNamedItem("Count").Value);
                    if (docTermFreqs.ContainsKey(docID))
                    {
                        Dictionary<int, int> termCountForDocs = docTermFreqs[docID];
                        if (!termCountForDocs.ContainsKey(termID))
                            termCountForDocs.Add(termID, count);
                        docTermFreqs[docID] = termCountForDocs;
                    }
                    else
                    {
                        Dictionary<int, int> termCountForDocs = new Dictionary<int, int>();
                        termCountForDocs.Add(termID, count);
                        docTermFreqs.Add(docID, termCountForDocs);
                    }

                }
            }
            return docTermFreqs;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int, double> ReadTermTfidf(string xmlFilePath)
        {
            Dictionary<int, double> termTfidfWeights = new Dictionary<int, double>();
            // termid -> (docid -> freq)
            Dictionary<int, Dictionary<int, int>> termDocFreqs = new Dictionary<int, Dictionary<int, int>>();
            Dictionary<int, List<int>> docTerms = new Dictionary<int, List<int>>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList docNodes = xDoc.SelectNodes("//Doc");
            List<int> allDocIDs = new List<int>();
            foreach (XmlNode docNode in docNodes)
            {
                int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                List<int> docTermIDs = new List<int>();
                if (docTerms.ContainsKey(docID))
                    docTermIDs = docTerms[docID];
                if (!allDocIDs.Contains(docID))
                    allDocIDs.Add(docID);
                XmlNodeList termNodes = docNode.SelectNodes("Term");
                foreach (XmlNode termNode in termNodes)
                {
                    int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                    int count = int.Parse(termNode.Attributes.GetNamedItem("Count").Value);
                    if (termDocFreqs.ContainsKey(termID))
                    {
                        Dictionary<int, int> termCountForDocs = termDocFreqs[termID];
                        if (!termCountForDocs.ContainsKey(docID))
                            termCountForDocs.Add(docID, count);
                    }
                    else
                    {
                        Dictionary<int, int> termCountForDocs = new Dictionary<int, int>();
                        termCountForDocs.Add(docID, count);
                        termDocFreqs.Add(termID, termCountForDocs);
                    }
                    if (!docTermIDs.Contains(termID))
                        docTermIDs.Add(termID);
                }
                if (docTerms.ContainsKey(docID))
                    docTerms[docID] = docTermIDs;
                else
                    docTerms.Add(docID, docTermIDs);
            }

            foreach (int termID in termDocFreqs.Keys)
            {
                int sumTermFreq = 0;
                int sumTermCount = 0;
                Dictionary<int, int> docTermFreq = termDocFreqs[termID];
                foreach (int docID in docTermFreq.Keys)
                {
                    sumTermFreq += docTermFreq[docID];
                    sumTermCount += docTerms[docID].Count;
                }
                double tf = (double)sumTermFreq / sumTermCount;
                double idf = Math.Log(((double)allDocIDs.Count / docTermFreq.Count), 2);
                double tfidf = tf * idf;
                termTfidfWeights.Add(termID, tfidf);
            }
            return termTfidfWeights;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,double> ReadTermWeights(string xmlFilePath)
        {
            Dictionary<int,double> termWeights=new Dictionary<int, double>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList termNodes = xDoc.SelectNodes("//Docs/Doc/Term");
            foreach(XmlNode termNode in termNodes)
            {
                int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                double weight = double.Parse(termNode.Attributes.GetNamedItem("Weight").Value);
                if(!termWeights.ContainsKey(termID))
                {
                    termWeights.Add(termID,weight);
                }
            }
            return termWeights;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int, TermPerformance> ReadTermPerformance(string xmlFilePath)
        {
            Dictionary<int, double> termTfidfs = ReadTermTfidf(xmlFilePath);
            Dictionary<int, double> clusterDistances = new Dictionary<int, double>();
            Dictionary<int, string> termPhrases = new Dictionary<int, string>();
            Dictionary<int, int> doc_cluster_mappings = new Dictionary<int, int>();
            Dictionary<int, Dictionary<int, double>> cluster_cluster_distances = new Dictionary<int, Dictionary<int, double>>();
            Dictionary<int, List<int>> term_Docs_Mappings = new Dictionary<int, List<int>>();
            Dictionary<int, List<int>> parent_child_clusters = new Dictionary<int, List<int>>();
            Dictionary<int, int> child_parent_clusters = new Dictionary<int, int>();

            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList clusterNodes = xDoc.SelectNodes("Clusters/Cluster");
            foreach (XmlNode clusterNode in clusterNodes)
            {
                int clusterID = int.Parse(clusterNode.Attributes.GetNamedItem("ClusterID").Value);
                double distance = double.Parse(clusterNode.Attributes.GetNamedItem("Distance").Value);
                if (!clusterDistances.ContainsKey(clusterID))
                    clusterDistances.Add(clusterID, distance);
                XmlNodeList docNodes = clusterNode.SelectNodes("Docs/Doc");
                if (docNodes != null && docNodes.Count > 0)
                {
                    foreach (XmlNode docNode in docNodes)
                    {
                        int docID = int.Parse(docNode.Attributes.GetNamedItem("DocID").Value);
                        if (!doc_cluster_mappings.ContainsKey(docID))
                            doc_cluster_mappings.Add(docID, clusterID);

                        XmlNodeList termNodes = docNode.SelectNodes("Term");
                        if (termNodes != null && termNodes.Count > 0)
                        {
                            foreach (XmlNode termNode in termNodes)
                            {
                                int termID = int.Parse(termNode.Attributes.GetNamedItem("TermID").Value);
                                string phrase = termNode.Attributes.GetNamedItem("Phrase").Value;
                                if (!termPhrases.ContainsKey(termID))
                                    termPhrases.Add(termID, phrase);
                                if (term_Docs_Mappings.ContainsKey(termID))
                                {
                                    List<int> docIDs = term_Docs_Mappings[termID];
                                    if (!docIDs.Contains(docID))
                                        docIDs.Add(docID);
                                    term_Docs_Mappings[termID] = docIDs;
                                }
                                else
                                {
                                    List<int> docIDs = new List<int>();
                                    docIDs.Add(docID);
                                    term_Docs_Mappings.Add(termID, docIDs);
                                }
                            }
                        }
                    }
                }

                XmlNodeList childClusterNodes = clusterNode.SelectNodes("ChildClusters/Cluster");
                if (childClusterNodes != null && childClusterNodes.Count > 0)
                {
                    foreach (XmlNode childClusterNode in childClusterNodes)
                    {
                        int childClusterID = int.Parse(childClusterNode.Attributes.GetNamedItem("ClusterID").Value);
                        child_parent_clusters.Add(childClusterID, clusterID);
                        if (parent_child_clusters.ContainsKey(clusterID))
                        {
                            List<int> childClusterIDs = parent_child_clusters[clusterID];
                            if (!childClusterIDs.Contains(childClusterID))
                                childClusterIDs.Add(childClusterID);
                            parent_child_clusters[clusterID] = childClusterIDs;
                        }
                        else
                        {
                            List<int> childClusterIDs = new List<int>();
                            childClusterIDs.Add(childClusterID);
                            parent_child_clusters.Add(clusterID, childClusterIDs);
                        }
                    }
                }
            }

            foreach (int fromClusterID in clusterDistances.Keys)
            {
                Dictionary<int, double> distancesForCluster = new Dictionary<int, double>();
                foreach (int toClusterID in clusterDistances.Keys)
                {
                    if (toClusterID == fromClusterID)
                    {
                        distancesForCluster.Add(toClusterID, 0);
                    }
                    else
                    {
                        if (child_parent_clusters.ContainsKey(fromClusterID) &&
                            child_parent_clusters[fromClusterID] == toClusterID)
                        {
                            distancesForCluster.Add(
                                toClusterID,
                                clusterDistances[fromClusterID] +
                                clusterDistances[toClusterID]);
                        }
                        else
                        {
                            distancesForCluster.Add(
                                toClusterID,
                                GetDistanceBetweenClusters(
                                    fromClusterID, toClusterID,
                                    clusterDistances,
                                    child_parent_clusters));
                        }
                    }
                }
                cluster_cluster_distances.Add(fromClusterID, distancesForCluster);
            }

            double totalDocTranversalDistance = 0;
            int[] allDocIDs = new int[doc_cluster_mappings.Count];
            doc_cluster_mappings.Keys.CopyTo(allDocIDs, 0);
            for (int i = 0; i < allDocIDs.Length; i++)
            {
                int fromClusterID = doc_cluster_mappings[allDocIDs[i]];
                for (int k = i + 1; k < allDocIDs.Length; k++)
                {
                    int toClusterID = doc_cluster_mappings[allDocIDs[k]];
                    totalDocTranversalDistance += cluster_cluster_distances[fromClusterID][toClusterID];
                }
            }
            double avgDocTranversalDistance = totalDocTranversalDistance / allDocIDs.Length;

            Dictionary<int, double> termScores = new Dictionary<int, double>();
            foreach (int termID in termPhrases.Keys)
            {
                double totalDocTranversalDistanceForTermContainingDocs = 0;
                List<int> positiveDocIDs = term_Docs_Mappings[termID];
                List<int> positiveClusterIDs = new List<int>();
                for (int i = 0; i < positiveDocIDs.Count; i++)
                {
                    int fromClusterID = doc_cluster_mappings[positiveDocIDs[i]];
                    if (!positiveClusterIDs.Contains(fromClusterID))
                        positiveClusterIDs.Add(fromClusterID);

                    for (int k = i + 1; k < positiveDocIDs.Count; k++)
                    {
                        int toClusterID = doc_cluster_mappings[positiveDocIDs[k]];
                        totalDocTranversalDistanceForTermContainingDocs +=
                            cluster_cluster_distances[fromClusterID][toClusterID];
                    }
                }
                double avgTermTranversalDistance =
                    totalDocTranversalDistanceForTermContainingDocs / positiveDocIDs.Count;

                double termPerformance =
                    Math.Pow((1 - avgTermTranversalDistance / avgDocTranversalDistance), 4) *
                    (1 - positiveClusterIDs.Count / clusterDistances.Count) *
                    Math.Log((double)positiveDocIDs.Count, 2) / Math.Log(allDocIDs.Length, 2);
                //double termPerformance =
                //    (1 - positiveClusterIDs.Count/clusterDistances.Count)*
                //    ((double) Math.Pow(positiveDocIDs.Count, 2)/Math.Log10(allDocIDs.Length));
                termScores.Add(termID, termPerformance);
            }

            Dictionary<int, TermPerformance> termPerformances = new Dictionary<int, TermPerformance>();
            foreach (int termID in termScores.Keys)
            {
                TermPerformance termPerformance = new TermPerformance();
                termPerformance.TermID = termID;
                termPerformance.ClassifierScore = termScores[termID];
                termPerformance.DocSupport = 0;
                termPerformance.ClusterSupport = 0;
                if (term_Docs_Mappings.ContainsKey(termID))
                {
                    List<int> docIDs = term_Docs_Mappings[termID];
                    termPerformance.DocSupport = docIDs.Count;
                    List<int> positiveClusterIDs = new List<int>();
                    foreach (int positiveDocID in docIDs)
                    {
                        if (!positiveClusterIDs.Contains(doc_cluster_mappings[positiveDocID]))
                            positiveClusterIDs.Add(doc_cluster_mappings[positiveDocID]);
                    }
                    termPerformance.ClusterSupport = positiveClusterIDs.Count;
                }
                termPerformance.Tfidf = termTfidfs[termID];
                termPerformance.Phrase = termPhrases[termID];
                termPerformances.Add(termID, termPerformance);
            }

            return termPerformances;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="xmlFilePath"></param>
        /// <returns></returns>
        public static Dictionary<int,Dictionary<int,double>> ReadClusterClusterDistances(string xmlFilePath)
        {
            Dictionary<int, Dictionary<int, double>> cluster_cluster_distances = new Dictionary<int, Dictionary<int, double>>();

            Dictionary<int, double> clusterDistances = new Dictionary<int, double>();
            Dictionary<int, int> child_parent_clusters = new Dictionary<int, int>();
            XmlDocument xDoc = new XmlDocument();
            xDoc.Load(xmlFilePath);
            XmlNodeList clusterNodes = xDoc.SelectNodes("Clusters/Cluster");
            foreach (XmlNode clusterNode in clusterNodes)
            {
                int clusterID = int.Parse(clusterNode.Attributes.GetNamedItem("ClusterID").Value);
                double distance = double.Parse(clusterNode.Attributes.GetNamedItem("Distance").Value);
                if (!clusterDistances.ContainsKey(clusterID))
                    clusterDistances.Add(clusterID, distance);

                XmlNodeList childClusterNodes = clusterNode.SelectNodes("ChildClusters/Cluster");
                if (childClusterNodes != null && childClusterNodes.Count > 0)
                {
                    foreach (XmlNode childClusterNode in childClusterNodes)
                    {
                        int childClusterID = int.Parse(childClusterNode.Attributes.GetNamedItem("ClusterID").Value);
                        child_parent_clusters.Add(childClusterID, clusterID);
                    }
                }
            }

            foreach (int fromClusterID in clusterDistances.Keys)
            {
                Dictionary<int, double> distancesForCluster = new Dictionary<int, double>();
                foreach (int toClusterID in clusterDistances.Keys)
                {
                    if (toClusterID == fromClusterID)
                    {
                        distancesForCluster.Add(toClusterID, 0);
                    }
                    else
                    {
                        if (child_parent_clusters.ContainsKey(fromClusterID) &&
                            child_parent_clusters[fromClusterID] == toClusterID)
                        {
                            distancesForCluster.Add(
                                toClusterID,
                                clusterDistances[fromClusterID] +
                                clusterDistances[toClusterID]);
                        }
                        else
                        {
                            distancesForCluster.Add(
                                toClusterID,
                                GetDistanceBetweenClusters(
                                    fromClusterID, toClusterID,
                                    clusterDistances,
                                    child_parent_clusters));
                        }
                    }
                }
                cluster_cluster_distances.Add(fromClusterID, distancesForCluster);
            }
            return cluster_cluster_distances;
        }

        private static double GetDistanceBetweenClusters(
            int fromClusterID, int toClusterID,
            Dictionary<int, double> clusterDistances,
            Dictionary<int, int> child_parent_clusters)
        {
            if (fromClusterID == toClusterID)
                return 0;
            if (child_parent_clusters.ContainsKey(fromClusterID) &&
                child_parent_clusters[fromClusterID] == toClusterID)
            {
                return clusterDistances[fromClusterID] + clusterDistances[toClusterID];
            }
            else
            {
                int commonAncestor = FindCommonAncestor(
                    fromClusterID, toClusterID,
                    child_parent_clusters);
                if (commonAncestor > 0)
                {
                    double distance = clusterDistances[fromClusterID];
                    int fromID1 = fromClusterID;
                    while (fromID1 != commonAncestor)
                    {
                        fromID1 = child_parent_clusters[fromID1];
                        distance += clusterDistances[fromID1];
                    }
                    int toID1 = toClusterID;
                    while (toID1 != commonAncestor)
                    {
                        distance += clusterDistances[toID1];
                        toID1 = child_parent_clusters[toID1];
                    }
                    return distance;
                }
                else
                {
                    return double.PositiveInfinity;
                }
            }
        }

        private static int FindCommonAncestor(int clusterID1, int clusterID2,
            Dictionary<int, int> child_parent_clusters)
        {
            List<int> ancestorsForCluster1 = new List<int>();
            int fromClusterID = clusterID1;
            ancestorsForCluster1.Add(fromClusterID);
            while (child_parent_clusters.ContainsKey(fromClusterID))
            {
                fromClusterID = child_parent_clusters[fromClusterID];
                ancestorsForCluster1.Add(fromClusterID);
            }

            int fromClusterID2 = clusterID2;
            while (child_parent_clusters.ContainsKey(fromClusterID2))
            {
                if (ancestorsForCluster1.Contains(fromClusterID2))
                    return fromClusterID2;

                fromClusterID2 = child_parent_clusters[fromClusterID2];
            }
            if (ancestorsForCluster1.Contains(fromClusterID2))
                return fromClusterID2;
            return 0;
        }
    }
}
